package com.fcml.study.algorithms;

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 3, 7, 15, 18, 26, 43, 66, 69, 80, 88, 89, 90, 92, 95, 99};
        System.out.println(commonBinarySearch(arr, 18));
        System.out.println(recursiveBinarySearch(arr, 0, arr.length - 1, 18));
    }

    private static int commonBinarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int mid;

        if (key < arr[low] || key > arr[high])
            return -1;

        while (low <= high) {
            mid = (low + high) / 2;
            if (key > arr[mid]) {
                low = mid + 1;
            } else if (key < arr[mid]) {
                high = mid - 1;
            } else return mid;
        }
        return -1;
    }

    private static int recursiveBinarySearch(int[] arr, int low, int high, int key) {
        if (key < arr[low] || key > arr[high])
            return -1;

        int mid = (low + high) / 2;
        if (key > arr[mid]) {
            return recursiveBinarySearch(arr, mid + 1, high, key);
        } else if (key < arr[mid]) {
            return recursiveBinarySearch(arr, low, mid - 1, key);
        } else return mid;
    }
}
